题解 bzoj4668冷战

发表于 | 更新于

有 $n$个点$,m $个操作，每次连接两个点，或者询问某两个点最早是在什么时刻开始连通的

并查集按秩合并$+LCA$找最大。

并查集按秩合并：复杂度为$O(nlogn)$，稍劣于路径压缩，但优点在于保留了树形结构，对于每个并查集记录一个值$rank$，初始值为$1$，表示树高，每次将$rank$小的并查集根节点合并到$rank$大的并查集根节点上(即把$f[find(x)]$赋值成$find(y))$，并将$v[x]$赋为$cnt$(即当前是第几次合并)这时$rank$不变，若两个并查集$rank$相同，则将一个合并到另一个,将$v[x]$赋值$,rank[find(y)]++;$

在$find$函数中，每次在回溯过程中更新每个点的一个值$deep$，表示它的深度$(deep[k]=deep[f[k]]+1;)$

若$opt=0$，每次用并查集按秩合并两个点.

若$opt=1$，则用暴力求$LCA$的方法从一个点不停的走向它的父亲，直到它的$deep\geqslant$另一个点的$deep$，此时若$deep[x]==deep[y]$,则退出，否则交换$x$与$y$，继续进行上述过程，直到$x==y$，在过程中不断更新$v[x]$的最大值，记录在变量$ans$中，并返回$ans$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define re register 
#define dd c=getchar()
using namespace std;
inline int read() {int s=0,w=1;char c;while (dd,c>'9' || c<'0') if (c=='-') w=-1;while (c>='0' && c<='9') s=s*10+c-'0',dd;return s*w;}
#undef dd
inline void write(int x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
inline void wln(int x) {write(x);puts("");}
int lastans,f[600000],cnt,dep[600000],v[600000],rank[600000];
int find(int k){
    if (f[k]==k)return k;
    int o=find(f[k]);
    dep[k]=dep[f[k]]+1;
    return o;
}
void merge(int x,int y,int z){
    x=find(x),y=find(y);
    if (x==y)return;
    if (rank[x]>rank[y])swap(x,y);
    if (rank[x]==rank[y])rank[y]++;
    f[x]=y;v[x]=z;
}
int lca(int x,int y){
    if (find(x)!=find(y))return 0;
    int ans=0;
    while (x!=y){
        if (dep[x]<dep[y])swap(x,y);
        ans=max(ans,v[x]);
        x=f[x];
    }
    return ans;
}
int main(){
    freopen("build.in","r",stdin);
    freopen("build.out","w",stdout);
    int n=read(),m=read();
    for (int i=1;i<=n;++i)f[i]=i,rank[i]=1;//初始化
    for (int i=1;i<=m;++i){
        int opt=read(),x=read()^lastans,y=read()^lastans;
        if (opt){
            lastans=lca(x,y);
            wln(lastans);
        }else{
            cnt++;
            merge(x,y,cnt);
        }
    }
    return 0;
}